`
https://leetcode.cn/problems/super-egg-drop/
`

/**
 * @param {number} k
 * @param {number} n
 * @return {number}
 */
var superEggDrop = function (k, n) {
  // 更具体的思路：https://labuladong.online/algo/dynamic-programming/egg-drop/

  // m 最多不会超过 N 次（线性扫描）
  const memo = Array.from({ length: k + 1 }, () => Array(n + 1).fill(-1));

  // 定义：手握 k 个鸡蛋，面对 n 层楼，最少的扔鸡蛋次数为 dp(k, n)
  function dp(K, N) {
    // base case
    if (K === 1) return N;
    if (N === 0) return 0;

    // 查备忘录避免冗余计算
    if (memo[K][N] !== -1) {
      return memo[K][N];
    }

    // 用二分搜索代替线性搜索
    let res = Infinity;
    let lo = 1, hi = N;
    while (lo <= hi) {
      const mid = lo + ((hi - lo) >> 1);
      // 鸡蛋在第 mid 层碎了和没碎两种情况
      const broken = dp(K - 1, mid - 1, memo);
      const notBroken = dp(K, N - mid, memo);
      // res = min(max(碎，没碎) + 1)
      if (broken > notBroken) {
        hi = mid - 1;
        res = Math.min(res, broken + 1);
      } else {
        lo = mid + 1;
        res = Math.min(res, notBroken + 1);
      }
    }

    // 结果存入备忘录
    memo[K][N] = res;
    return res;
  }

  return dp(k, n);
};